package xin.luna.exercise;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * Chapter 1 Section 3 Exercise 29: 用环形链表实现Queue
 *
 * @param <Item>
 */
public class C1S3E29<Item> {
  public static void main(String[] args) {
    C1S3E29<String> queue = new C1S3E29<>();

    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals("-")) {
        queue.enqueue(item);
      } else if (!queue.isEmpty()) {
        StdOut.print(queue.dequeue() + "  ");
      }
    }

    StdOut.println("(" + queue.size() + " left on queue)");
  }

  private Node last;

  private int length;

  public boolean isEmpty() {
    return 0 == length;
  }

  public int size() {
    return length;
  }

  public void enqueue(Item item) {
    Node node = new Node();
    node.item = item;

    if (isEmpty()) {
      last = node;
      last.next = node;
    } else {
      Node first = last.next;
      last.next = node;
      node.next = first;
      last = node;
    }

    length++;
  }

  public Item dequeue() {
    Item item = last.next.item;
    last.next = last.next.next;

    length--;

    return item;
  }

  private class Node {
    Item item;
    Node next;
  }
}
